package top.interview.string

import problem.Problem

class Q139WordBreak extends Problem {
  def wordBreak(s: String, wordDict: List[String]): Boolean = {
    breakDp(s, wordDict.toSet)
  }

  def break0(s: String, wordDict: Set[String], start: Int): Boolean = {
    if (s.length == start) true
    else {
      ((start + 1) to s.length).exists { i =>
        val s0 = s.substring(start, i)
        if (wordDict.contains(s0)) break0(s, wordDict, i)
        else false
      }
    }
  }

  def breakDp(s: String, wordDict: Set[String]): Boolean = {
    val dp = Array.ofDim[Int](s.length, s.length + 1)
    break1(s, wordDict, 0, dp)
  }

  def break1(s: String, wordDict: Set[String], start: Int, dp: Array[Array[Int]]): Boolean = {
    if (s.length == start) true
    else {
      ((start + 1) to s.length).exists { i =>
        if (dp(start)(i) != 0) {
          dp(start)(i) == 1
        } else {
          val s0 = s.substring(start, i)
          if (wordDict.contains(s0)) {
            if (break1(s, wordDict, i, dp)) {
              dp(start)(i) = 1
            } else {
              dp(start)(i) = -1
            }
            dp(start)(i) == 1
          } else {
            dp(start)(i) = -1
            false
          }
        }
      }
    }
  }

  override def test(): Unit = {
    val cases = Table(("string", "dict", "match"),
      ("leetcode", List("leet", "code"), true),
      ("applepenapple", List("apple", "pen"), true),
      ("catsandog", List("cats", "dog", "sand", "and", "cat"), false),
      ("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab",
        List("a", "aa", "aaa", "aaaa", "aaaaa", "aaaaaa", "aaaaaaa", "aaaaaaaa", "aaaaaaaaa",
          "aaaaaaaaaa"), false),
      ("aaaaaaa", List("aaaa", "aa"), false)
    )
    forAll(cases) { (s, dict, isMatch) =>
      wordBreak(s, dict) shouldBe isMatch
    }
  }
}
